#include <iostream>

using namespace std;

template<class Type>
class SeqList {
protected:        //SeqList类的数据成员
    Type *data; //顺序表存储数组(指针方式定义)
    int MaxSize;    //最大允许长度(元素个数)
    int last;                    //最后一个元素的下标

public:            //SeqList类的函数成员
    SeqList(int ListSize);             //构造函数
    ~SeqList() { delete[] data; }             //析构函数
    int Length() const { return last + 1; }

    int Locate(Type &x) const;                    //定位
    int Insert(int i, Type x);                    //插入
    int Delete(int i);                             //删除
    int Next(Type x, Type &next);       //后继
    int Prior(Type x, Type &pre);        //前驱
    int Empty() { return last == -1; }      //判空
    int Full() { return last == MaxSize - 1; }

    Type Get(int i) {                               //提取
        return i < 0 || i > last ? NULL : data[i];
    }

    void ShowSqlist() {
        int i;
        for (i = 0; i < last; i++) {
            cout << data[i] << "-->";
            if (i % 5 == 4) cout << endl;
        }
        cout << data[i] << endl;
    }
};


template<class Type>
SeqList<Type>::SeqList(int ListSize) {
    //创建一个最大长度为ListSize的空线性表
    if (ListSize > 0) {
        MaxSize = ListSize;
        last = -1;
        //申请分配内存空间
        data = new Type[MaxSize];
        //空间申请失败处理
        if (data == NULL) {
            MaxSize = 0;
        }
    }
}

template<class Type>
int SeqList<Type>::Locate(Type &x) const {
    //查找函数：在顺序表中从前向后查找元素值
    //等于给定值x的数据元素,返回所在单元下标
    int i = 0;
    while (i <= last && data[i] != x)
        i++;
    if (i > last) return -1;     //返回-1表示查找失败
    else return i;
}

template<class Type>
int SeqList<Type>::Insert(int i, Type x) {
    //判断删除位置i是否合理以及表是否已满
    if (i < 0 || i > last + 1 || last == MaxSize - 1)
        return 0;                //插入操作不成功
    else {
        last++;
        for (int j = last; j > i; j--) {
            data[j] = data[j - 1];     //元素后移
        }
        data[i] = x;
        return 1;    //操作成功
    }
}

template<class Type>
int SeqList<Type>::Delete(int i) {
    //判断插入位置i是否合理,表是否为空表
    if (i < 0 || i > last || last < 0) return 0;
    //数据元素前移
    for (int j = i + 1; j <= last; j++)
        data[j - 1] = data[j];    //元素前移(覆盖)
    last--;
    return 1;                   //成功删除
}


void Union(SeqList<int> &A,
           SeqList<int> &B) {
    int n = A.Length();
    int m = B.Length();
    for (int i = 0; i < m; i++) {
        int x = B.Get(i);         //在B中取一元素
        int k = A.Locate(x);     //在A中搜索它
        if (k == -1)              //若未找到,插入元素
        {
            A.Insert(n, x);
            n++;
        }
    }
}

void Intersection(SeqList<int> &A,
                  SeqList<int> &B) {
    int n = A.Length();
    int m = B.Length();
    int i = 0;
    while (i < n) {
        int x = A.Get(i);             //在A中取一元素
        int k = B.Locate(x);       //在B中搜索它
        if (k == -1) {
            A.Delete(i);
            n--;
        }
        else i++;                    //未找到，在A中删除它
    }
}


int main() {
    SeqList<int> list(10);
    list.Insert(0, 1);
    list.Insert(0, 2);
    list.Insert(0, 3);
    list.Insert(0, 4);
    list.ShowSqlist();

    int a = list.Get(2);

}

